package pers.vic.basics.leetcode;

import java.time.Period;
import java.util.*;

/**
 * @description: 496. 下一个更大元素 I {@literal https://leetcode-cn.com/problems/next-greater-element-i/}
 * @author Vic.xu
 * @date: 2021/1/22 0022 16:57
 */
public class J0496_E_NextGreaterElement {
    /*
    给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
    请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
    nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
     */

    /**
     * 开始使用单调栈
     */
    public static  int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //nums1 转map  item -> index
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }
        int[] result = new int[nums1.length];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums2.length; i++) {
            //当前预算小于栈顶元素的时候  不符合更大  则出栈
            while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                Integer index = map.get(nums2[stack.peek()]);
                if (index != null) {
                    result[index] =nums2[i];
                }
                stack.pop();
            }
            stack.push(i);
        }

        return result;
    }

    public static void main(String[] args) {
        /*
        输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1]

        输入: nums1 = [2,4], nums2 = [1,2,3,4].输出: [3,-1]
         */
        System.out.println(Arrays.toString(nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2})));
        System.out.println(Arrays.toString(nextGreaterElement(new int[]{2,4}, new int[]{1,2,3,4})));

        System.out.println(Arrays.toString(dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));

    }

    public static  int[] dailyTemperatures(int[] T) {
        int len = T.length;
        // 为空
        if (len == 0) {
            return T;
        }
        Stack<Integer> stack = new Stack<>();
        //返回数组
        int[] arr = new int[len];
        int t = 0;
        for (int i = 0; i < len; i++) {
            // 维护单调栈
            while (!stack.isEmpty() && T[i] > T[stack.peek()]){
                //赋值给数组
                arr[stack.peek()] = i - stack.pop();
            }
            // 入栈的为下标，这里需要注意
            stack.push(i);
        }
        return arr;
    }

}
